package graph;

import java.util.*;

public class DijkstraLinked {
    // Graph class
    static class Graph {
        int V; // number of vertices
        LinkedList<Node>[] adjList; // adjacency list

        // Node class
        static class Node implements Comparable<Node> {
            int vertex; // vertex number
            int weight; // weight to vertex

            Node(int v, int w) {
                vertex = v;
                weight = w;
            }

            // compareTo method for priority queue
            public int compareTo(Node other) {
                return Integer.compare(weight, other.weight);
            }
        }

        // Graph constructor
        Graph(int v) {
            V = v;
            adjList = new LinkedList[V];
            for (int i = 0; i < V; i++) {
                adjList[i] = new LinkedList<>();
            }
        }

        // add edge to graph
        void addEdge(int u, int v, int w) {
            adjList[u].add(new Node(v, w));
            adjList[v].add(new Node(u, w));
        }

        // Dijkstra's algorithm
        void dijkstra(int start) {
            // initialize distances and visited array
            int[] dist = new int[V];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[start] = 0;
            boolean[] visited = new boolean[V];

            // create priority queue and add starting node
            PriorityQueue<Node> pq = new PriorityQueue<>();
            pq.add(new Node(start, 0));

            // loop until priority queue is empty
            while (!pq.isEmpty()) {
                // remove node with minimum distance
                int u = pq.poll().vertex;
                visited[u] = true;

                // update distances for adjacent nodes
                for (Node n : adjList[u]) {
                    int v = n.vertex;
                    int w = n.weight;
                    if (!visited[v] && dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.add(new Node(v, dist[v]));
                    }
                }
            }

            // print shortest distances
            System.out.println("Shortest distances from vertex " + start + ":");
            for (int i = 0; i < V; i++) {
                System.out.println("Vertex " + i + ": " + dist[i]);
            }
        }
    }

    // main method
    public static void main(String[] args) {
        // create graph
        Graph g = new Graph(5);
        g.addEdge(0, 1, 9);
        g.addEdge(0, 2, 6);
        g.addEdge(0, 3, 5);
        g.addEdge(0, 4, 3);
        g.addEdge(2, 1, 2);
        g.addEdge(2, 3, 4);

        // run Dijkstra's algorithm from vertex 0
        g.dijkstra(0);
    }
}
